home *** CD-ROM | disk | FTP | other *** search
/ Komputer for Alle 2004 #2 / K-CD-2-2004.ISO / OpenOffice Sv / f_0397 / python-core-2.2.2 / lib / sre_parse.py < prev    next >
Encoding:
Python Source  |  2003-07-18  |  24.1 KB  |  739 lines
  1. #
  2. # Secret Labs' Regular Expression Engine
  3. #
  4. # convert re-style regular expression to sre pattern
  5. #
  6. # Copyright (c) 1998-2001 by Secret Labs AB.  All rights reserved.
  7. #
  8. # See the sre.py file for information on usage and redistribution.
  9. #
  10.  
  11. """Internal support module for sre"""
  12.  
  13. # XXX: show string offset and offending character for all errors
  14.  
  15. # this module works under 1.5.2 and later.  don't use string methods
  16. import string, sys
  17.  
  18. from sre_constants import *
  19.  
  20. SPECIAL_CHARS = ".\\[{()*+?^$|"
  21. REPEAT_CHARS = "*+?{"
  22.  
  23. DIGITS = tuple("0123456789")
  24.  
  25. OCTDIGITS = tuple("01234567")
  26. HEXDIGITS = tuple("0123456789abcdefABCDEF")
  27.  
  28. WHITESPACE = tuple(" \t\n\r\v\f")
  29.  
  30. ESCAPES = {
  31.     r"\a": (LITERAL, ord("\a")),
  32.     r"\b": (LITERAL, ord("\b")),
  33.     r"\f": (LITERAL, ord("\f")),
  34.     r"\n": (LITERAL, ord("\n")),
  35.     r"\r": (LITERAL, ord("\r")),
  36.     r"\t": (LITERAL, ord("\t")),
  37.     r"\v": (LITERAL, ord("\v")),
  38.     r"\\": (LITERAL, ord("\\"))
  39. }
  40.  
  41. CATEGORIES = {
  42.     r"\A": (AT, AT_BEGINNING_STRING), # start of string
  43.     r"\b": (AT, AT_BOUNDARY),
  44.     r"\B": (AT, AT_NON_BOUNDARY),
  45.     r"\d": (IN, [(CATEGORY, CATEGORY_DIGIT)]),
  46.     r"\D": (IN, [(CATEGORY, CATEGORY_NOT_DIGIT)]),
  47.     r"\s": (IN, [(CATEGORY, CATEGORY_SPACE)]),
  48.     r"\S": (IN, [(CATEGORY, CATEGORY_NOT_SPACE)]),
  49.     r"\w": (IN, [(CATEGORY, CATEGORY_WORD)]),
  50.     r"\W": (IN, [(CATEGORY, CATEGORY_NOT_WORD)]),
  51.     r"\Z": (AT, AT_END_STRING), # end of string
  52. }
  53.  
  54. FLAGS = {
  55.     # standard flags
  56.     "i": SRE_FLAG_IGNORECASE,
  57.     "L": SRE_FLAG_LOCALE,
  58.     "m": SRE_FLAG_MULTILINE,
  59.     "s": SRE_FLAG_DOTALL,
  60.     "x": SRE_FLAG_VERBOSE,
  61.     # extensions
  62.     "t": SRE_FLAG_TEMPLATE,
  63.     "u": SRE_FLAG_UNICODE,
  64. }
  65.  
  66. # figure out best way to convert hex/octal numbers to integers
  67. try:
  68.     int("10", 8)
  69.     atoi = int # 2.0 and later
  70. except TypeError:
  71.     atoi = string.atoi # 1.5.2
  72.  
  73. class Pattern:
  74.     # master pattern object.  keeps track of global attributes
  75.     def __init__(self):
  76.         self.flags = 0
  77.         self.open = []
  78.         self.groups = 1
  79.         self.groupdict = {}
  80.     def opengroup(self, name=None):
  81.         gid = self.groups
  82.         self.groups = gid + 1
  83.         if name:
  84.             ogid = self.groupdict.get(name, None)
  85.             if ogid is not None:
  86.                 raise error, ("redefinition of group name %s as group %d; "
  87.                               "was group %d" % (repr(name), gid,  ogid))
  88.             self.groupdict[name] = gid
  89.         self.open.append(gid)
  90.         return gid
  91.     def closegroup(self, gid):
  92.         self.open.remove(gid)
  93.     def checkgroup(self, gid):
  94.         return gid < self.groups and gid not in self.open
  95.  
  96. class SubPattern:
  97.     # a subpattern, in intermediate form
  98.     def __init__(self, pattern, data=None):
  99.         self.pattern = pattern
  100.         if not data:
  101.             data = []
  102.         self.data = data
  103.         self.width = None
  104.     def dump(self, level=0):
  105.         nl = 1
  106.         for op, av in self.data:
  107.             print level*"  " + op,; nl = 0
  108.             if op == "in":
  109.                 # member sublanguage
  110.                 print; nl = 1
  111.                 for op, a in av:
  112.                     print (level+1)*"  " + op, a
  113.             elif op == "branch":
  114.                 print; nl = 1
  115.                 i = 0
  116.                 for a in av[1]:
  117.                     if i > 0:
  118.                         print level*"  " + "or"
  119.                     a.dump(level+1); nl = 1
  120.                     i = i + 1
  121.             elif type(av) in (type(()), type([])):
  122.                 for a in av:
  123.                     if isinstance(a, SubPattern):
  124.                         if not nl: print
  125.                         a.dump(level+1); nl = 1
  126.                     else:
  127.                         print a, ; nl = 0
  128.             else:
  129.                 print av, ; nl = 0
  130.             if not nl: print
  131.     def __repr__(self):
  132.         return repr(self.data)
  133.     def __len__(self):
  134.         return len(self.data)
  135.     def __delitem__(self, index):
  136.         del self.data[index]
  137.     def __getitem__(self, index):
  138.         return self.data[index]
  139.     def __setitem__(self, index, code):
  140.         self.data[index] = code
  141.     def __getslice__(self, start, stop):
  142.         return SubPattern(self.pattern, self.data[start:stop])
  143.     def insert(self, index, code):
  144.         self.data.insert(index, code)
  145.     def append(self, code):
  146.         self.data.append(code)
  147.     def getwidth(self):
  148.         # determine the width (min, max) for this subpattern
  149.         if self.width:
  150.             return self.width
  151.         lo = hi = 0L
  152.         for op, av in self.data:
  153.             if op is BRANCH:
  154.                 i = sys.maxint
  155.                 j = 0
  156.                 for av in av[1]:
  157.                     l, h = av.getwidth()
  158.                     i = min(i, l)
  159.                     j = max(j, h)
  160.                 lo = lo + i
  161.                 hi = hi + j
  162.             elif op is CALL:
  163.                 i, j = av.getwidth()
  164.                 lo = lo + i
  165.                 hi = hi + j
  166.             elif op is SUBPATTERN:
  167.                 i, j = av[1].getwidth()
  168.                 lo = lo + i
  169.                 hi = hi + j
  170.             elif op in (MIN_REPEAT, MAX_REPEAT):
  171.                 i, j = av[2].getwidth()
  172.                 lo = lo + long(i) * av[0]
  173.                 hi = hi + long(j) * av[1]
  174.             elif op in (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY):
  175.                 lo = lo + 1
  176.                 hi = hi + 1
  177.             elif op == SUCCESS:
  178.                 break
  179.         self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint))
  180.         return self.width
  181.  
  182. class Tokenizer:
  183.     def __init__(self, string):
  184.         self.string = string
  185.         self.index = 0
  186.         self.__next()
  187.     def __next(self):
  188.         if self.index >= len(self.string):
  189.             self.next = None
  190.             return
  191.         char = self.string[self.index]
  192.         if char[0] == "\\":
  193.             try:
  194.                 c = self.string[self.index + 1]
  195.             except IndexError:
  196.                 raise error, "bogus escape (end of line)"
  197.             char = char + c
  198.         self.index = self.index + len(char)
  199.         self.next = char
  200.     def match(self, char, skip=1):
  201.         if char == self.next:
  202.             if skip:
  203.                 self.__next()
  204.             return 1
  205.         return 0
  206.     def get(self):
  207.         this = self.next
  208.         self.__next()
  209.         return this
  210.     def tell(self):
  211.         return self.index, self.next
  212.     def seek(self, index):
  213.         self.index, self.next = index
  214.  
  215. def isident(char):
  216.     return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"
  217.  
  218. def isdigit(char):
  219.     return "0" <= char <= "9"
  220.  
  221. def isname(name):
  222.     # check that group name is a valid string
  223.     if not isident(name[0]):
  224.         return 0
  225.     for char in name:
  226.         if not isident(char) and not isdigit(char):
  227.             return 0
  228.     return 1
  229.  
  230. def _group(escape, groups):
  231.     # check if the escape string represents a valid group
  232.     try:
  233.         gid = atoi(escape[1:])
  234.         if gid and gid < groups:
  235.             return gid
  236.     except ValueError:
  237.         pass
  238.     return None # not a valid group
  239.  
  240. def _class_escape(source, escape):
  241.     # handle escape code inside character class
  242.     code = ESCAPES.get(escape)
  243.     if code:
  244.         return code
  245.     code = CATEGORIES.get(escape)
  246.     if code:
  247.         return code
  248.     try:
  249.         if escape[1:2] == "x":
  250.             # hexadecimal escape (exactly two digits)
  251.             while source.next in HEXDIGITS and len(escape) < 4:
  252.                 escape = escape + source.get()
  253.             escape = escape[2:]
  254.             if len(escape) != 2:
  255.                 raise error, "bogus escape: %s" % repr("\\" + escape)
  256.             return LITERAL, atoi(escape, 16) & 0xff
  257.         elif str(escape[1:2]) in OCTDIGITS:
  258.             # octal escape (up to three digits)
  259.             while source.next in OCTDIGITS and len(escape) < 5:
  260.                 escape = escape + source.get()
  261.             escape = escape[1:]
  262.             return LITERAL, atoi(escape, 8) & 0xff
  263.         if len(escape) == 2:
  264.             return LITERAL, ord(escape[1])
  265.     except ValueError:
  266.         pass
  267.     raise error, "bogus escape: %s" % repr(escape)
  268.  
  269. def _escape(source, escape, state):
  270.     # handle escape code in expression
  271.     code = CATEGORIES.get(escape)
  272.     if code:
  273.         return code
  274.     code = ESCAPES.get(escape)
  275.     if code:
  276.         return code
  277.     try:
  278.         if escape[1:2] == "x":
  279.             # hexadecimal escape
  280.             while source.next in HEXDIGITS and len(escape) < 4:
  281.                 escape = escape + source.get()
  282.             if len(escape) != 4:
  283.                 raise ValueError
  284.             return LITERAL, atoi(escape[2:], 16) & 0xff
  285.         elif escape[1:2] == "0":
  286.             # octal escape
  287.             while source.next in OCTDIGITS and len(escape) < 4:
  288.                 escape = escape + source.get()
  289.             return LITERAL, atoi(escape[1:], 8) & 0xff
  290.         elif escape[1:2] in DIGITS:
  291.             # octal escape *or* decimal group reference (sigh)
  292.             here = source.tell()
  293.             if source.next in DIGITS:
  294.                 escape = escape + source.get()
  295.                 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
  296.                     source.next in OCTDIGITS):
  297.                     # got three octal digits; this is an octal escape
  298.                     escape = escape + source.get()
  299.                     return LITERAL, atoi(escape[1:], 8) & 0xff
  300.             # got at least one decimal digit; this is a group reference
  301.             group = _group(escape, state.groups)
  302.             if group:
  303.                 if not state.checkgroup(group):
  304.                     raise error, "cannot refer to open group"
  305.                 return GROUPREF, group
  306.             raise ValueError
  307.         if len(escape) == 2:
  308.             return LITERAL, ord(escape[1])
  309.     except ValueError:
  310.         pass
  311.     raise error, "bogus escape: %s" % repr(escape)
  312.  
  313. def _parse_sub(source, state, nested=1):
  314.     # parse an alternation: a|b|c
  315.  
  316.     items = []
  317.     while 1:
  318.         items.append(_parse(source, state))
  319.         if source.match("|"):
  320.             continue
  321.         if not nested:
  322.             break
  323.         if not source.next or source.match(")", 0):
  324.             break
  325.         else:
  326.             raise error, "pattern not properly closed"
  327.  
  328.     if len(items) == 1:
  329.         return items[0]
  330.  
  331.     subpattern = SubPattern(state)
  332.  
  333.     # check if all items share a common prefix
  334.     while 1:
  335.         prefix = None
  336.         for item in items:
  337.             if not item:
  338.                 break
  339.             if prefix is None:
  340.                 prefix = item[0]
  341.             elif item[0] != prefix:
  342.                 break
  343.         else:
  344.             # all subitems start with a common "prefix".
  345.             # move it out of the branch
  346.             for item in items:
  347.                 del item[0]
  348.             subpattern.append(prefix)
  349.             continue # check next one
  350.         break
  351.  
  352.     # check if the branch can be replaced by a character set
  353.     for item in items:
  354.         if len(item) != 1 or item[0][0] != LITERAL:
  355.             break
  356.     else:
  357.         # we can store this as a character set instead of a
  358.         # branch (the compiler may optimize this even more)
  359.         set = []
  360.         for item in items:
  361.             set.append(item[0])
  362.         subpattern.append((IN, set))
  363.         return subpattern
  364.  
  365.     subpattern.append((BRANCH, (None, items)))
  366.     return subpattern
  367.  
  368. def _parse(source, state):
  369.     # parse a simple pattern
  370.  
  371.     subpattern = SubPattern(state)
  372.  
  373.     while 1:
  374.  
  375.         if source.next in ("|", ")"):
  376.             break # end of subpattern
  377.         this = source.get()
  378.         if this is None:
  379.             break # end of pattern
  380.  
  381.         if state.flags & SRE_FLAG_VERBOSE:
  382.             # skip whitespace and comments
  383.             if this in WHITESPACE:
  384.                 continue
  385.             if this == "#":
  386.                 while 1:
  387.                     this = source.get()
  388.                     if this in (None, "\n"):
  389.                         break
  390.                 continue
  391.  
  392.         if this and this[0] not in SPECIAL_CHARS:
  393.             subpattern.append((LITERAL, ord(this)))
  394.  
  395.         elif this == "[":
  396.             # character set
  397.             set = []
  398. ##          if source.match(":"):
  399. ##              pass # handle character classes
  400.             if source.match("^"):
  401.                 set.append((NEGATE, None))
  402.             # check remaining characters
  403.             start = set[:]
  404.             while 1:
  405.                 this = source.get()
  406.                 if this == "]" and set != start:
  407.                     break
  408.                 elif this and this[0] == "\\":
  409.                     code1 = _class_escape(source, this)
  410.                 elif this:
  411.                     code1 = LITERAL, ord(this)
  412.                 else:
  413.                     raise error, "unexpected end of regular expression"
  414.                 if source.match("-"):
  415.                     # potential range
  416.                     this = source.get()
  417.                     if this == "]":
  418.                         if code1[0] is IN:
  419.                             code1 = code1[1][0]
  420.                         set.append(code1)
  421.                         set.append((LITERAL, ord("-")))
  422.                         break
  423.                     else:
  424.                         if this[0] == "\\":
  425.                             code2 = _class_escape(source, this)
  426.                         else:
  427.                             code2 = LITERAL, ord(this)
  428.                         if code1[0] != LITERAL or code2[0] != LITERAL:
  429.                             raise error, "bad character range"
  430.                         lo = code1[1]
  431.                         hi = code2[1]
  432.                         if hi < lo:
  433.                             raise error, "bad character range"
  434.                         set.append((RANGE, (lo, hi)))
  435.                 else:
  436.                     if code1[0] is IN:
  437.                         code1 = code1[1][0]
  438.                     set.append(code1)
  439.  
  440.             # XXX: <fl> should move set optimization to compiler!
  441.             if len(set)==1 and set[0][0] is LITERAL:
  442.                 subpattern.append(set[0]) # optimization
  443.             elif len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
  444.                 subpattern.append((NOT_LITERAL, set[1][1])) # optimization
  445.             else:
  446.                 # XXX: <fl> should add charmap optimization here
  447.                 subpattern.append((IN, set))
  448.  
  449.         elif this and this[0] in REPEAT_CHARS:
  450.             # repeat previous item
  451.             if this == "?":
  452.                 min, max = 0, 1
  453.             elif this == "*":
  454.                 min, max = 0, MAXREPEAT
  455.  
  456.             elif this == "+":
  457.                 min, max = 1, MAXREPEAT
  458.             elif this == "{":
  459.                 here = source.tell()
  460.                 min, max = 0, MAXREPEAT
  461.                 lo = hi = ""
  462.                 while source.next in DIGITS:
  463.                     lo = lo + source.get()
  464.                 if source.match(","):
  465.                     while source.next in DIGITS:
  466.                         hi = hi + source.get()
  467.                 else:
  468.                     hi = lo
  469.                 if not source.match("}"):
  470.                     subpattern.append((LITERAL, ord(this)))
  471.                     source.seek(here)
  472.                     continue
  473.                 if lo:
  474.                     min = atoi(lo)
  475.                 if hi:
  476.                     max = atoi(hi)
  477.                 if max < min:
  478.                     raise error, "bad repeat interval"
  479.             else:
  480.                 raise error, "not supported"
  481.             # figure out which item to repeat
  482.             if subpattern:
  483.                 item = subpattern[-1:]
  484.             else:
  485.                 item = None
  486.             if not item or (len(item) == 1 and item[0][0] == AT):
  487.                 raise error, "nothing to repeat"
  488.             if item[0][0] in (MIN_REPEAT, MAX_REPEAT):
  489.                 raise error, "multiple repeat"
  490.             if source.match("?"):
  491.                 subpattern[-1] = (MIN_REPEAT, (min, max, item))
  492.             else:
  493.                 subpattern[-1] = (MAX_REPEAT, (min, max, item))
  494.  
  495.         elif this == ".":
  496.             subpattern.append((ANY, None))
  497.  
  498.         elif this == "(":
  499.             group = 1
  500.             name = None
  501.             if source.match("?"):
  502.                 group = 0
  503.                 # options
  504.                 if source.match("P"):
  505.                     # python extensions
  506.                     if source.match("<"):
  507.                         # named group: skip forward to end of name
  508.                         name = ""
  509.                         while 1:
  510.                             char = source.get()
  511.                             if char is None:
  512.                                 raise error, "unterminated name"
  513.                             if char == ">":
  514.                                 break
  515.                             name = name + char
  516.                         group = 1
  517.                         if not isname(name):
  518.                             raise error, "bad character in group name"
  519.                     elif source.match("="):
  520.                         # named backreference
  521.                         name = ""
  522.                         while 1:
  523.                             char = source.get()
  524.                             if char is None:
  525.                                 raise error, "unterminated name"
  526.                             if char == ")":
  527.                                 break
  528.                             name = name + char
  529.                         if not isname(name):
  530.                             raise error, "bad character in group name"
  531.                         gid = state.groupdict.get(name)
  532.                         if gid is None:
  533.                             raise error, "unknown group name"
  534.                         subpattern.append((GROUPREF, gid))
  535.                         continue
  536.                     else:
  537.                         char = source.get()
  538.                         if char is None:
  539.                             raise error, "unexpected end of pattern"
  540.                         raise error, "unknown specifier: ?P%s" % char
  541.                 elif source.match(":"):
  542.                     # non-capturing group
  543.                     group = 2
  544.                 elif source.match("#"):
  545.                     # comment
  546.                     while 1:
  547.                         if source.next is None or source.next == ")":
  548.                             break
  549.                         source.get()
  550.                     if not source.match(")"):
  551.                         raise error, "unbalanced parenthesis"
  552.                     continue
  553.                 elif source.next in ("=", "!", "<"):
  554.                     # lookahead assertions
  555.                     char = source.get()
  556.                     dir = 1
  557.                     if char == "<":
  558.                         if source.next not in ("=", "!"):
  559.                             raise error, "syntax error"
  560.                         dir = -1 # lookbehind
  561.                         char = source.get()
  562.                     p = _parse_sub(source, state)
  563.                     if not source.match(")"):
  564.                         raise error, "unbalanced parenthesis"
  565.                     if char == "=":
  566.                         subpattern.append((ASSERT, (dir, p)))
  567.                     else:
  568.                         subpattern.append((ASSERT_NOT, (dir, p)))
  569.                     continue
  570.                 else:
  571.                     # flags
  572.                     if not FLAGS.has_key(source.next):
  573.                         raise error, "unexpected end of pattern"
  574.                     while FLAGS.has_key(source.next):
  575.                         state.flags = state.flags | FLAGS[source.get()]
  576.             if group:
  577.                 # parse group contents
  578.                 if group == 2:
  579.                     # anonymous group
  580.                     group = None
  581.                 else:
  582.                     group = state.opengroup(name)
  583.                 p = _parse_sub(source, state)
  584.                 if not source.match(")"):
  585.                     raise error, "unbalanced parenthesis"
  586.                 if group is not None:
  587.                     state.closegroup(group)
  588.                 subpattern.append((SUBPATTERN, (group, p)))
  589.             else:
  590.                 while 1:
  591.                     char = source.get()
  592.                     if char is None:
  593.                         raise error, "unexpected end of pattern"
  594.                     if char == ")":
  595.                         break
  596.                     raise error, "unknown extension"
  597.  
  598.         elif this == "^":
  599.             subpattern.append((AT, AT_BEGINNING))
  600.  
  601.         elif this == "$":
  602.             subpattern.append((AT, AT_END))
  603.  
  604.         elif this and this[0] == "\\":
  605.             code = _escape(source, this, state)
  606.             subpattern.append(code)
  607.  
  608.         else:
  609.             raise error, "parser error"
  610.  
  611.     return subpattern
  612.  
  613. def parse(str, flags=0, pattern=None):
  614.     # parse 're' pattern into list of (opcode, argument) tuples
  615.  
  616.     source = Tokenizer(str)
  617.  
  618.     if pattern is None:
  619.         pattern = Pattern()
  620.     pattern.flags = flags
  621.     pattern.str = str
  622.  
  623.     p = _parse_sub(source, pattern, 0)
  624.  
  625.     tail = source.get()
  626.     if tail == ")":
  627.         raise error, "unbalanced parenthesis"
  628.     elif tail:
  629.         raise error, "bogus characters at end of regular expression"
  630.  
  631.     if flags & SRE_FLAG_DEBUG:
  632.         p.dump()
  633.  
  634.     if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE:
  635.         # the VERBOSE flag was switched on inside the pattern.  to be
  636.         # on the safe side, we'll parse the whole thing again...
  637.         return parse(str, p.pattern.flags)
  638.  
  639.     return p
  640.  
  641. def parse_template(source, pattern):
  642.     # parse 're' replacement string into list of literals and
  643.     # group references
  644.     s = Tokenizer(source)
  645.     p = []
  646.     a = p.append
  647.     def literal(literal, p=p):
  648.         if p and p[-1][0] is LITERAL:
  649.             p[-1] = LITERAL, p[-1][1] + literal
  650.         else:
  651.             p.append((LITERAL, literal))
  652.     sep = source[:0]
  653.     if type(sep) is type(""):
  654.         makechar = chr
  655.     else:
  656.         makechar = unichr
  657.     while 1:
  658.         this = s.get()
  659.         if this is None:
  660.             break # end of replacement string
  661.         if this and this[0] == "\\":
  662.             # group
  663.             if this == "\\g":
  664.                 name = ""
  665.                 if s.match("<"):
  666.                     while 1:
  667.                         char = s.get()
  668.                         if char is None:
  669.                             raise error, "unterminated group name"
  670.                         if char == ">":
  671.                             break
  672.                         name = name + char
  673.                 if not name:
  674.                     raise error, "bad group name"
  675.                 try:
  676.                     index = atoi(name)
  677.                 except ValueError:
  678.                     if not isname(name):
  679.                         raise error, "bad character in group name"
  680.                     try:
  681.                         index = pattern.groupindex[name]
  682.                     except KeyError:
  683.                         raise IndexError, "unknown group name"
  684.                 a((MARK, index))
  685.             elif len(this) > 1 and this[1] in DIGITS:
  686.                 code = None
  687.                 while 1:
  688.                     group = _group(this, pattern.groups+1)
  689.                     if group:
  690.                         if (s.next not in DIGITS or
  691.                             not _group(this + s.next, pattern.groups+1)):
  692.                             code = MARK, group
  693.                             break
  694.                     elif s.next in OCTDIGITS:
  695.                         this = this + s.get()
  696.                     else:
  697.                         break
  698.                 if not code:
  699.                     this = this[1:]
  700.                     code = LITERAL, makechar(atoi(this[-6:], 8) & 0xff)
  701.                 if code[0] is LITERAL:
  702.                     literal(code[1])
  703.                 else:
  704.                     a(code)
  705.             else:
  706.                 try:
  707.                     this = makechar(ESCAPES[this][1])
  708.                 except KeyError:
  709.                     pass
  710.                 literal(this)
  711.         else:
  712.             literal(this)
  713.     # convert template to groups and literals lists
  714.     i = 0
  715.     groups = []
  716.     literals = []
  717.     for c, s in p:
  718.         if c is MARK:
  719.             groups.append((i, s))
  720.             literals.append(None)
  721.         else:
  722.             literals.append(s)
  723.         i = i + 1
  724.     return groups, literals
  725.  
  726. def expand_template(template, match):
  727.     g = match.group
  728.     sep = match.string[:0]
  729.     groups, literals = template
  730.     literals = literals[:]
  731.     try:
  732.         for index, group in groups:
  733.             literals[index] = s = g(group)
  734.             if s is None:
  735.                 raise IndexError
  736.     except IndexError:
  737.         raise error, "empty group"
  738.     return string.join(literals, sep)
  739.